package com.gaofeng.algo.kt

import java.util.*

fun permute(nums: IntArray): List<List<Int?>>? {
    val answer: MutableList<List<Int?>> = ArrayList()
    val output: MutableList<Int?> = ArrayList()
    for (num in nums) {
        output.add(num)
    }
    val n = nums.size
    backtrack(n, answer, output, 0)
    return answer
}

private fun backtrack(n: Int, ans: MutableList<List<Int?>>, output: List<Int?>, first: Int) {
    if (first == n) {
        ans.add(ArrayList(output))
        return
    }
    for (i in first until n) {
        Collections.swap(output, i, first)
        backtrack(n, ans, output, first + 1)
        Collections.swap(output, i, first)
    }
}